'''
https://leetcode.cn/problems/palindromic-substrings/
'''

class Solution:

    # i >= r. radius从1开始扩
    # i < r: 根据对称性可的
    #       1) i+p[i_prime] < r: p[i] = p[i_prime]
    #       2) i+p[i_prime] > r: p[i] = r-i
    #       1) i+p[i_prime] = r: p[i] = 至少为(p[i_prime]=r-i)，可能还可以继续扩
    def countSubstrings(self, s: str) -> int:
        s = '#' + '#'.join(s) + '#'
        n = len(s)
        p = [0] * n         # 回文半径数组
        center, r = 0, 0    # 之前扩的最远右边界的中心位置，以及他扩到的右边界（不包含右边界，即多扩一位）
        for i in range(n):
            i_prime = 2 * center - i
            radius = min(p[i_prime], r - i) if i < r else 1
            while i - radius >= 0 and i + radius < n and s[i - radius] == s[i + radius]:
                radius += 1
            p[i] = radius
            if i + radius > r:
                center, r = i, i + radius
        # 新字符串回文半径(多+了1)，对应原回文串的回文长度+1
        # // 2, 就是一侧的长度，[a',c,a], 是回文
        #           则，[a'+1,c,a-1], 也是回文
        #           则，[a'+2,c,a-2], 也是回文
        # 所以//2就可以获得原字符串以这个位置为中心的回文数量
        return sum(t // 2 for t in p)

